package isCovered;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        // 暴力 哈希表
//        Set<Integer> set = new HashSet<>(); // 区间包含的
//        for (int[] range: ranges) {
//            for (int i = range[0]; i <=range[1] ; i++) {
//                set.add(i);
//            }
//        }
//        for (int i = left; i <= right; i++) {
//            if(!set.contains(i)){
//                return false;
//            }
//        }
//        return true;

        // 数组替代哈希表
//        int[] marks = new int[51];
//        for (int[] range: ranges) {
//            for (int i = range[0]; i <=range[1] ; i++) {
//                marks[i]++;
//            }
//        }
//        for (int i = left; i <= right; i++) {
//            if(marks[i]==0){
//                return false;
//            }
//        }
//        return true;

        // 差分数组
        int[] cnt = new int[52];
        for (int[] range: ranges) {
            cnt[range[0]]++;
            cnt[range[1]+1]--;
        }
        for (int i = 1; i < cnt.length; i++) {
            cnt[i] = cnt[i-1] + cnt[i];
        }
        for (int i = left; i <= right; i++) {
            if(cnt[i]==0){
                return false;
            }
        }
        return true;
    }
}
